\documentclass[12pt,lettersize,oneside]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage{longtable}
\usepackage[hyphens]{url}
\usepackage{listings}
\usepackage{anysize}
\usepackage{float}

\lstset{
  language=C,
  basicstyle=\small
}
\usepackage[pdftex]{graphicx}
\usepackage{color}
\definecolor{gray75}{gray}{.75}
\lstdefinestyle{consola}
{basicstyle=\small\bf\ttfamily,
backgroundcolor=\color{gray75},
}
\lstdefinestyle{consola2}
{basicstyle=\footnotesize\bf\ttfamily,
backgroundcolor=\color{gray75},
}
%\pagestyle{fancy}


\title{Grupo 5 \\ Soluciones Metaheurísticas Para el Problema de Clustering}
\author{Carlos Colmenares \and Kelwin Fernández}
\begin{document}
\maketitle
\setlength{\parskip}{2.5mm}
\setlength{\itemsep}{0ex }

\newpage

\tableofcontents

\newpage

\section{Descripción y Formulación del Problema de Clustering} \label{DescripcionYFormulacion}

El problema de clustering consiste en realizar una partición de un
conjunto, cuyos elementos son observaciones de algún tipo, de tal manera que los elementos en cada subconjunto
de la partición se asemejen unos a otros de cierta manera, mientras que los elementos
en subconjuntos distintos deben parecerse lo menos posible. Se denomina ``cluster'' a cada
subconjunto de dicha partición.

Formalmente, podemos definir al problema de la siguiente manera:

\begin{itemize}
\item Sea $D$ un conjunto de observaciones.
\item Sea $\Pi(D)$ el conjunto de todas las particiones de $D$.
\item Sea $\Pi_k(D)$ el conjunto de todas las \emph{k-particiones}
de $D$, donde una \emph{k-partición} es una partición de un conjunto en 'k' partes.
\item Sea $f: \Pi(D) \rightarrow \mathbb{R}$ una función que mida la \emph{bondad} \footnote{Refiérase a la sección
\ref{CalidadSolucion} para un mayor análisis de dicha función de bondad} de una partición, donde una partición $A$ es mejor que otra $B$
si y sólo si $f(A) > f(B)$.

\end{itemize}

El problema general de Clustering consistirá entonces en conseguir una partición $p \in \Pi(D)$ tal que:

$$ \forall q \in \Pi(D), f(q) \le f(p) $$

Una primera variación del problema correspondería a fijar el número de particiones que debe tener
la solución, formalmente:

Dado un $n \in \mathbb{N}$ tal que $1 \le n \le |D|$, el problema de Clustering consiste en conseguir una
partición $p \in \Pi_n(D)$ tal que:

\begin{equation} \label{eq:clusteringProblem}
\forall q \in \Pi_n(D), f(q) \le f(p)
\end{equation}

\subsection{Clustering Numérico y Categórico}

El subconjunto $D$ consiste en diversas ``observaciones'', cada una de dichas
observaciones se puede representar como un conjunto de datos. Cada uno de estos datos
puede ser continuo o discreto. Se denomina entonces \emph{Clustering Numérico} al problema
de clustering en donde todos los datos de las observaciones son continuos, y \emph{Clustering Categórico}
a aquel cuyos datos son en su totalidad discretos. Obviamente también existirán instancias de problema
cuyas observaciones presenten datos tanto continuos como discretos, sin embargo es más interesante
estudiar los problemas en los que todos los datos son de un tipo u otro pues para resolver los
casos mixtos sólo se necesitará aplicar una solución que aplique una mezcla de las técnicas
usadas para resolver cada caso por separado.

\subsection{Nivel de Calidad de una Solución} \label{CalidadSolucion}

El proceso de medir una solución siempre consta de dos fases:

\begin{itemize}

\item \textbf{Distancia intra-cluster}, la cual es una medida de la calidad de un cluster
dependiendo de la cercanía de los datos que se encuentren dentro de éste. En otras palabras,
mide qué tan relacionados están los datos que pertenecen a un mismo cluster. Esto implica que
se de debe contar con alguna función
$d: D x D \rightarrow \mathbb{R}$ que mida la cercanía de dos puntos cualesquiera.

\item \textbf{Distancia inter-cluster}, la cual es una medida de la semejanza
entre dos clusters. Esto implica que se debe contar con alguna función
$h: P(D) x P(D) \rightarrow \mathbb{R}$ que mida la cercanía de dos clusters cualesquiera.

\end{itemize} 

Generalmente la calidad de una solución sería una operación en función de todas las distancias inter e intra-cluster.
Dependiendo de esta medida, las soluciónes  preferidas serán aquellas que contengan clusters que estén dispersos o cercanos, o
que tengan puntos muy semejantes o muy diferentes.

Esta definición tan libre y ``etérea'' de la medida de calidad de una solución hace que el problema de Clustering
sea muy variable, difícil, diverso, y a su vez interesante. Comúnmente para cierta medida de calidad determinadas
técnicas funcionan a la perfección para encontrar una buena solución, pero si se cambia dicha medida, la técnica
podría dejar de ser buena.

\subsection{Aplicaciones del problema}

El problema tiene diversas aplicaciones en muchas áreas de la ciencia, a continuación se mencionan algunas de ellas:

\begin{description}
  \item[Biología] \hfill \\
    Normalmente la técnica es usada para clasificar ciertos especímenes de alguna población:
    de cada espécimen se toman diversas medidas de su fenotipo (tamaño, peso, etc.), después de
    realizar la clasificación, se espera que cada cluster contenga especímenes que se relacionen
    de alguna manera peculiar. De esta forma se pueden encontrar patrones escondidos en el fenotipo
    de los especímenes, lo que puede llevar a descubrimientos más interesantes.

  \item[Mercadotecnia] \hfill \\
    La clasificación en clusters es muy usada en mercadotecnia cuando se trabaja con problemas
    de variable múltiple provenientes de distintos tipos de encuestas.

  \item[Medicina] \hfill \\
     Un ejemplo popular de la aplicación del problema es el de lograr encontrar patrones
     para diferenciar distintos tipos de tejido y sangre en una imagen médica en 3D.
  
  \item[Aprendizaje de Máquina] \hfill \\
    El problema se usa directamente para resolver problemas de aprendizaje no-supervisado, el
    cuál implica encontrar patrones escondidos entre datos que no se conoce cómo se relacionan.
\end{description}

\section{Detalles de la Representación del Problema}

Debido a la diversidad del problema, y con el fin de acotar las
variaciones y tipos de los casos de prueba, se decidió que los problemas
a tratar serán sólo de clusters numéricos. Adicionalmente, también se
decidió que el problema a resolver será aquel en el cual el número de clusters que
se desea que tenga la solución es una cifra conocida, es decir, se solucionará
el problema que corresponde a la ecuación \eqref{eq:clusteringProblem} de
la sección \ref{DescripcionYFormulacion}.

\subsection{Representación de la Solución} 

De entre todas las formas posibles de representar una solución, se
decidió que esta fuera en función de \textbf{centroides}; debido a que los problemas
tratados son de clusters numéricos, se puede pensar que cada observación es un punto
en un plano cartesiano \emph{N-dimensional}, donde N es la cantidad de datos o medidas
dentro de la observación. Consecuentemente denominamos un \textbf{centroide} a un punto
en dicho plano que representa el ``centro'' de un cluster: un punto pertenece al cluster cuyo
centroide esté más cercano a él. Una solución a un problema será entonces representada por
los centroides de cada cluster que se desee que tenga la solución final.

\subsubsection{Notación}

De ahora en adelante se nombrará $c_i$ al centroide del cluster número $i$, en donde
$i \in {1,2,...,n}$.

Se denominará $C$ a un conjunto de $n$ clusters, es decir: $C = \{c_1,c_2,...,c_n\}$.

Dado un conjunto de centroides $C$, la función $\alpha$ se
define como la función que dado un conjunto de centroides y un punto
$\vec{x} \in D$, retorna el centroide al cual $\vec{x}$ es más cercano. Formalmente:

$$ \alpha(C,\vec{x}) = \min\limits_{1 \le i \le n} d(c_i,\vec{x})  $$

Donde $d$ es una función que mide la distancia entre dos puntos. Esta función
será descrita en la sección \ref{CercaniaDosPuntos}.

Para hacer referencia a todos los puntos que pertenezcan a un cluster, se usará
la notación $D_{c_i}$. Este conjunto se define formalmente como:

$$ D_{c_i} = \{\vec{x} \in D\ |\ \alpha(C,\vec{x}) = c_i\}$$.

Como se mencionó en la sección \ref{DescripcionYFormulacion}, una solución al 
problema es una partición del conjunto $D$. De manera que se nombrará al conjunto
$S_D(C)$ como la partición del conjunto $D$ inducida por los centroides $c_1,c_2,...,c_n$,
formalmente:

$$ S_D(C) = \{D_{c_1},D_{c_2},...,D_{c_n}\}$$

\subsection{Función Objetivo} 

Tal como se mencionó en la sección \ref{CalidadSolucion}, la función que se
intentará optimizar es una combinación entre las distancias intra e inter-clusters
de los datos. Para ambas distancias es necesario contar con un método para medir
la ``cercanía'' de dos puntos.

\subsubsection{Cercanía de Dos Puntos} \label{CercaniaDosPuntos}

Es necesario contar con una función
$d: D x D \rightarrow \mathbb{R}$ que mida de cierta manera qué tan cercanas o parecidas
son dos observaciones de la instancia del problema. Dado que se interpretarán
dichas observaciones como puntos en un plano cartesiano \emph{N-dimensional},
dicha función $d$ se puede implementar de distintas maneras:

Sea $\vec{x} = \{x_1,x_2,...,x_n\}$ y $\vec{y} = \{y_1,y_2,...,y_n\}$ dos puntos en 
un plano cartesiano \emph{N-dimensional}, la distancia $d(\vec{x},\vec{y})$ se
puede calcular cómo:

\begin{description}
  \item[Distancia euclideana] \hfill \\
    $$d(\vec{x},\vec{y}) = \sqrt[2]{\displaystyle\sum\limits_{i=1}^n (x_i-y_i)^2 }$$

  \item[Distancia manhattan] \hfill \\
    $$d(\vec{x},\vec{y}) = \displaystyle\sum\limits_{i=1}^n |x_i-y_i| $$


  \item[Norma máxima] \hfill \\
    $$d(\vec{x},\vec{y}) = \max\limits_{1 \le i \le n} |x_i-y_i| $$
  
  \item[Distancia de mahalanobis] \hfill \\
    Sea $S$ la matriz de covarianza de los datos (los datos son todas las observaciones
    de la instancia del problema)
    $$d(\vec{x},\vec{y}) = \sqrt[2]{ (\vec{x} -\vec{y})^T S^{-1} (\vec{x} -\vec{y}) }$$

\end{description}

Existen muchísimas otras medidas que pueden ser utilizadas para estos casos, sin embargo
las mencionadas anteriormente son las más comunes y populares.

\subsubsection{Distancia Intra-Cluster}

Esta distancia es una medida del nivel se ``semejanza'' entre todos los puntos
que pertenecen a un cluster. Se denominará $\sigma_i$ a la distancia intra-cluster del cluster
inducido por el centroide $c_i$.
Existen varias maneras de medir dicha distancia, sin embargo, las más comunes
son las siguientes:

\begin{description}
  \item[Promedio de distancias] \hfill \\
    Se define como el promedio de la distancia entre el centroide de un cluster
    y todos los puntos que pertenecen a éste, formalmente:

    $$\sigma_i = \frac{1}{|D_{c_i}|} \displaystyle\sum\limits_{\vec{x} \in D_{c_i}} d(c_i,\vec{x}) $$

  \item[Distancia máxima] \hfill \\
    Se define como la máxima distancia entre el centroide de un cluster y cualquiera de sus puntos,
    formalmente:

    $$\sigma_i = \max\limits_{\vec{x} \in D_{c_i} } d(c_i,\vec{x}) $$


\end{description}

Dado que los puntos que pertenezcan a un cluster deben de ser muy ``similares'' o muy ``cercanos'',
se desea que estos clusters sean tan compactos como sea posible. Dado que la distancia Intra-Cluster mide
exactamente qué tan compacto es un cluster, siempre se buscará minimizar dicha medida a todos los
clusters por igual.

\subsubsection{Distancia Inter-Cluster}

Esta es una medida del nivel de ``semejanza'' o ``cercanía'' entre
dos clusters, y se denotará con la función $h(D_{c_i},D_{c_j})$. A continuación se describen
distintos métodos de calcularla:


\begin{description}
  \item[Distancia entre centroides] \hfill \\
    Dado que un cluster es inducido por su centroide, se puede definir consecuentemente
    la distancia entre dos clusters como la distancia entre sus centroides, formalmente:

    $$h(D_{c_i},D_{c_j}) = d(c_i,c_j)$$

  \item[Promedio de distancias] \hfill \\
    Corresponde al promedio de la distancia entre los puntos de ambos clusters, formalmente:

    $$h(D_{c_i},D_{c_j}) = \frac{1}{|D_{c_i}||D_{c_j}|} \displaystyle\sum\limits_{\vec{x} \in D_{c_i}, \vec{y} \in D_{c_j}} d(\vec{x},\vec{y}) $$

\end{description}

Cuando se divide a todas las observaciones en clusters, siempre se desea que estos clusters sean tan distantes
como sea posible, es decir, se desea que los puntos que pertenezcan a un cluster sean muy distantes o muy diferentes
de los puntos que pertenecen a cualquier otro cluster.
Dado que la distancia inter-cluster mide la separación o nivel de diferencia entre dos clusters, siempre se buscará
maximizar la distancia inter-cluster de todos los clusters por igual.

\subsubsection{Función de Calidad de Solución} \label{FuncionCalidad}

La función de calidad de solución es la \textbf{función objetivo}, es decir,
la función que se intentará de optimizar. 

Al poder calcular la distancia intra-cluster e inter-cluster, la calidad
de la solución es una relación entre estas medidas. A continuación se describen
dos de los métodos más populares para calcular dicha relación. Cabe destacar
que dependiendo de la medida que se use, ``mejorar'' la calidad significará
maximizar o minimizar la función.

\begin{description}
  \item[Método de Davies–Bouldin] \hfill \\
    Este método realiza un promedio entre valores que se asignan a cada cluster. Estos valores serán una relación entre
    las medidas inter e intra-cluster con respecto a todos los otros clusters. Se calcula de la siguiente manera:

    $$f( S_D(C) ) = \frac{1}{n} \displaystyle\sum\limits_{i=1}^n \left ( \max\limits_{1 \le j \le n, i \ne j} \frac{\sigma_i+\sigma_j}{h(D_{c_i},D_{c_j})}\right ) $$

    Dado que se desea tener clusters compactos y separados, es decir, valores pequeños de distancias intra-cluster y valores
    altos de distancias inter-cluster, con este método una solución $S_D(C)$ será mejor que otra solución $S_D(C')$ si
    $f( S_D(C) ) < f( S_D(C') )$.

  \item[Método de Dunn] \hfill \\
    Este método obtiene una relación entre la máxima distancia Intra-cluster (la cual se desea minimizar), y la
    mínima distancia Inter-Cluster (La cual se desea maximizar). Se calcula de la siguiente manera:

    $$f( S_D(C) ) = \frac{ \min\limits_{1 \le i,j \le n,\ i \ne j} h(D_{c_i},D_{c_j})} { \max\limits_{1 \le k \le n} \sigma_k } $$

    Dado que se desea que las distancias Inter-Clusters sean grandes, y las distancias Intra-Clusters sean pequeñas,
    con este método una solución $S_D(C)$ será mejor que otra solución $S_D(C')$ si
    $f( S_D(C) ) > f( S_D(C') )$.

\end{description}

\subsubsection{Funciones Objetivos implementadas}

En la solución que se implementó para el problema de clustering, se implementaron las siguientes
funciones de medición de calidad de una solución:

\begin{itemize}
    \item \textbf{Método de Davies–Bouldin}: Con medidas Intra-Cluster por \emph{promedio de distancias}
    y medidas Inter-Cluster por \emph{distancia entre centroides}.
    \item \textbf{Método de Dunn}: Con medidas Intra-Cluster por \emph{distancia máxima}
    y medidas Inter-Cluster por \emph{distancia entre centroides}.
\end{itemize}

\subsection{Operadores de Vecindad}

Se implementaron dos operadores distintos de vecindad:

\begin{itemize}
    \item \textbf{Aproximación de centroides}: Se definió la función $acercar(c_i,\vec{x}) = \frac{1}{2}(c_i+\vec{x})$,
    la cual ``acerca'' un centroide a un punto (lo aproxima a la mitad de la distancia entre ellos). La vecindad de
    un estado es entonces todas las otras soluciones que difieren de la primera por haber ``acercado'' uno de
    los centroides a algún punto. Consecuentemente la vecindad contará con $n|D|$ soluciones, ya que cada ``vecino''
    corresponde a acercar un centroide a alguna de las observaciones.
    \item \textbf{Aproximación suave de centroides}: Este operador de vecindad funciona bajo el mismo principio
    que el anterior: la vecindad de una solución sería equivalente a $n|D|$ otras soluciones, cada una correspondiente
    a aproximar un centroide a alguna observación. La función $acercar(c_i,\vec{x})$ también fue implementada de
    la misma manera que para la vecindad anterior. La única diferencia entre ambos operadores, es que en este caso
    antes de ``acercar'' el centroide a alguna observación, primero se calcula el \textbf{centro geométrico} del cluster,
    luego se traslada el centroide a dicho centro, y posteriormente se realiza la operación de acercarlo a la
    observación especificada. Como se puede ver en la sección \ref{Resultados}, en algunos casos esta
    vecindad generó mejores resultados que la anterior.
\end{itemize}

\section{Descripción de las Metaheurísticas de Trayectoria Implementadas}

Se aplicaron diversas metaheurísticas para intentar resolver el 
problema de \emph{Clustering Numérico}. A continuación se presentan dichas metaheurísticas
y se describe un pequeño pseudo-código de las mismas.

\subsection{Búsqueda Local (LS)} \label{LS}

Búsqueda Local es una metaheurítica de trayectoria bastante sencilla pues
sólo realiza intensificación y nunca diversificación. El pseudo-código
del procedimiento implementado es el siguiente:

\begin{verbatim}
( 1) proc busqueda_local():
( 2)     S <- solución_Inicial()
( 3)     mientras( no criterio_de_parada ) hacer
( 4)         S' <- obtener_mejor_vecino(S)
( 5)         si criterio_de_aceptación(S,S') entonces
( 6)             S <- S'
( 7)         si_no
( 8)             retornar S
( 9)         fin_si
(10)     fin_mientras
(11)     retornar S
(12) fin_proc
\end{verbatim}

A continuación se realizará una explicación de las subrutinas implementadas:

\begin{itemize}
    \item En la línea (2), la solución inicial consiste en seleccionar $n$ puntos al azar
    entre todas las observaciones y colocar un centroide sobre cada uno de dichos puntos.
    Donde $n$ es el número de clusters que se desea que tenga la solución.
    \item En la línea (3), el criterio de parada implementado fue solamente un
    contador de iteraciones. De modo que el algoritmo detiene su ejecución después
    de ese número de ciclos.
    \item En la línea (4), se calcula toda la vecindad del estado $S$ y se
    selecciona la mejor de ellas. El mejor vecino es aquel cuyo valor de
    calidad es el menor o el mayor de todos; esta selección depende completamente
    de la técnica implementada para la función de calidad, tal como se describe en la
    sección \ref{FuncionCalidad}.
    \item En la línea (5), la función ``criterio\_de\_aceptación'' recibe dos soluciones
    ``a'' y ``b'', y retorna \emph{cierto} si ``b'' es una mejor solución que ``a'', de lo
    contrario retorna \emph{falso}. Nuevamente, esta selección depende de la implementación
    de la medida de calidad de una solución que se utilice.
\end{itemize}

Como podemos apreciar, cuando ningún vecino de la solución actual es mejor que dicha
solución, entonces el algoritmo detiene su ejecución debido a que se ha encontrado un óptimo local.

\subsection{Búsqueda Local Iterada (ILS)}

La Búsqueda Local Iterada es una metaheurítica de trayectoria basada
en la búsqueda local, con la diferencia que esta no sólo realiza intensificación
si no también diversificación. El pseudo-código
del procedimiento implementado es el siguiente:

\begin{verbatim}
( 1) proc búsqueda_local_iterada():
( 2)     S <- solución_Inicial()
( 3)     S* <- búsqueda_local(S)
( 4)     Sm <- S*
( 5)     mientras( no criterio_de_parada ) hacer
( 6)         S' <- perturbar(S*)
( 7)         S'* <- búsqueda_local(S')
( 8)         si criterio_de_aceptación(Sm,S'*) entonces
( 9)             Sm <- S'*
(10)         fin_si
(11)         S* <- S'*
(12)     fin_mientras
(13)     retornar Sm
(14) fin_proc
\end{verbatim}

A continuación se realizará una explicación de las subrutinas utilizadas:

\begin{itemize}
    \item En la línea 2, la subrutina llamada ``búsqueda\_local(S)'' es la misma
    búsqueda local descrita en la sección \ref{LS} con la diferencia de que
    el estado inicial no es uno al azar si no el estado que se pasa como argumento.
    \item En la línea 5, el criterio de parada es un número máximo de iteraciones predefinido.
    A diferencia de la búsqueda local simple, este algoritmo realizará siempre todas las iteraciones
    y no se detiene al encontrar un mínimo local.
    \item En la línea 6, la subrutina ``perturbar'' toma una solución y la cambia un poco. Esto se
    implementó haciendo que se cambiaran de posición la mitad de los centroides a una nueva
    posición aleatoria.
    \item En la línea 8, la subrutina ``criterio\_de\_aceptación'' es la misma que la
    definida en la sección \ref{LS} para una búsqueda local.
\end{itemize}

A diferencia de la búsqueda local, la búsqueda local iterada realiza diversificación:
el algoritmo comienza con un estado al azar y realiza una búsqueda local. Al encontrar un
mínimo local, el algoritmo repetitivamente perturba la solución (que estaba en un mínimo local),
y vuelve a aplicar búsqueda local. La solución final será la mejor de todas las encontradas.

\subsection{Búsqueda Tabú (TS)}

La búsqueda tabú se diferencia de otras metaheurísticas pues implementa una memoria a corto
plazo. Dicha memoria se utiliza para ``recordar'' los más recientes vecinos que se han elegido para
intensificar la búsqueda (mejorarla);
cuando esto sucede, se dice que el vecino es \textbf{tabú} por cierto tiempo determinado. Cuando
se genera la vecindad de un estado, se deben eliminar de dicha vecindad todos los vecinos que
son tabú para evitar tomar decisiones repetidas, sin importar si estos vecinos \textbf{tabú}
son los mejores de la vecindad o no.

A continuación se describe el pseudo-código de la rutina implementada:

\begin{verbatim}
( 1) proc búsqueda_tabú_memoria_corto_plazo():
( 2)     ListaTabú <- nueva_lista_tabú() 
( 3)     S <- solución_inicial()
( 4)     mientras( no criterio_de_parada ) hacer
( 5)         S' <- obtener_mejor_vecino_no_tabú(S,ListaTabú)
( 6)         si criterio_de_aceptación(S,S') entonces
( 7)             hacerTabú(S,S',ListaTabú)
( 8)             S <- S'
( 9)         si_no
(10)             retornar S
(11)         fin_si
(12)         envejecer(ListaTabú)
(13)     fin_mientras
(14)     retornar S
(15) fin_proc
\end{verbatim}

Como podemos ver, el procedimiento es muy parecido a una búsqueda local
simple pero con el añadido de la lista tabú. A continuación se
describen las subrutinas del procedimiento:

\begin{itemize}
    \item En la línea 2, se inicializa una lista tabú, la cuál es una estructura
    que puede almacenar de alguna manera tuplas del tipo (Estado,Vecino) y a su
    vez asignarles una vejez. Esta vejez es simplemente un recordatorio de
    cuánto tiempo o iteraciones lleva dicha tupla en memoria.
    \item En las líneas 3, 4, y 6, el método para obtener una solución inicial,
    criterio de parada, y criterio de aceptación son iguales a los descritos en la búsqueda local de la
    sección \ref{LS}.
    \item En la línea 5, el procedimiento de obtener el mejor vecino no tabú es
    muy parecido al método de ``obtener\_mejor\_vecino'' de la búsqueda local con la
    diferencia de que se usa la lista tabú para extraer de dicha vecindad los vecinos
    que estén tabú, es decir, se evita ir a un mismo vecino al cual se haya ido anteriormente.
    \item En la línea 7, se puede apreciar que cuando se toma la decisión de ir a un
    vecino se coloca en la lista tabú dicha decisión para evitarla en el futuro.
    \item En la línea 12, se envejece la lista tabú. Este envejecimiento hace que
    los vecinos tabú que tengan ya cierto tiempo en la tabla sean eliminados de ella. Se
    denomina ``tamaño de la memoria a corto plazo'' a dicho valor que indica cuánto tiempo
    podría permanecer un vecino tabú en la lista.
\end{itemize}

En la implementación que se hizo del algoritmo, dado que un vecino de un estado se genera al 
acercar uno de sus centroides a una de las observaciones, la lista tabú se aplicó como
una tabla de hash que admite tuplas (centroide,punto), de manera que cuando un centroide
se acerca a un punto no se permite realizar dicha operación nuevamente (acercarlo más)
hasta cierto número de iteraciones en el futuro.

Ahora bien, se puede apreciar que la búsqueda tabú descrita anteriormente sólo realiza
intensificación, más no diversificación. Para resolver dicho problema se incluye la
noción de memoria a largo plazo, la cual se basa en obtener 
un conjunto de mejores soluciones, llamadas élites, y posteriormente tratar de mejorarlas.
La solución final será la mejor de todas las élites. A continuación el pseudo-código
del procedimiento:

\begin{verbatim}
( 1) proc búsqueda_tabú_memoria_largo_plazo():
( 2)     ListaÉlites <- nueva_cola()
( 3)     repetir TamañoMemoriaLargoPlazo veces
( 4)         Élite <- búsqueda_tabú_memoria_corto_plazo()
( 5)         encolar(ListaÉlites,Élite)
( 6)     fin_repetir
( 7)     Sm <- NULO
( 8)     mientras( no criterio_de_parada y no vacía(ListaÉlites) ) hacer
( 9)         Élite <- desencolar(ListaÉlites)
(10)         Élite* <- búsqueda_tabú_memoria_corto_plazo(Élite)
(11)         si criterio_de_aceptación(Élite,Élite*) entonces
(12)             encolar(Élite*, ListaÉlites)
(13)         fin_si
(14)         si criterio_de_aceptación(Sm,Élite*) entonces
(15)             Sm <- Élite*
(16)         fin_si
(17)     fin_mientras
(18)     retornar Sm
(19) fin_proc
\end{verbatim}
 
Todas las subrutinas son iguales a las descritas anteriormente. Adicionalmente
la llamada al procedimiento ``búsqueda\_tabú\_memoria\_corto\_plazo(Élite)''
en la línea 10, sería equivalente a hacer la búsqueda tabú a corto plazo
pero no con un estado al azar si no con el estado que se pasa como parámetro.

Podemos apreciar que el procedimiento genera un número inicial de élites
y luego trata progresivamente de mejorarlas.

\subsection{Búsqueda por Vecindades Variables (VNS)}

Esta metaheurística, básicamente consiste en una extensión de
\textit{Local Search}, considerando una secuencia de vecindades
a analizar, en cada paso, la metaheurística explorará cada una
de las vecindades hasta lograr aceptar un vecino. El pseudo-código
del procedimiento implementado es el siguiente:

\begin{verbatim}
( 1) proc busqueda_por_vecindades_variables():
( 2)     S <- solución_Inicial()
( 3)     mientras( no criterio_de_parada ) hacer
( 4)         k <- 1
( 5)         repetir hasta k = MAX
( 6)         S' <- obtener_mejor_vecino(N(k,S))
( 5)         si criterio_de_aceptación(S,S') entonces
( 6)             S <- S'
( 8)             break
( 9)         si_no
(10)             retornar S
(11)         fin_si
(12)     fin_mientras
(13)     retornar S
(14) fin_proc
\end{verbatim}

Las vecindades utilizadas en la metaheurística se corresponden
con las explicadas anteriormente en la sección de operadores
de vecindad.

\subsection{Búsqueda de K-Medias (K-means)}

El algoritmo de las k-Medias, mejor conocido por su nombre en
inglés \textit{k-means}, se trata de un algoritmo de trayectoria
especializado en el problema de clustering. Este utiliza como
heurística de optimización ajustar cada centroide a su centro
de masa hasta punto fijo.

En nuestro caso, lo utilizamos para intensificar las soluciones
obtenidas por las distintas metaheurísticas, si bien no es
como tal una metaheurística, se coloca en esta sección por formar
parte del banco de algoritmos implementados en el presente
proyecto.

A continuación se presenta el pseudo-código del algoritmo:

\begin{verbatim}
( 1) proc k_means():
( 2)     S <- solución_Inicial()
( 3)     S* <- S
( 4)     mientras( no criterio_de_parada ) hacer
( 5)         asignar_centroide_mas_cercano(S)
( 6)         S <- recomputar_centroides(S)
( 7)         si criterio_de_aceptación(S*,S) entonces
( 8)             S* <- S
( 9)         fin_si
(10)     fin_mientras
(11)     retornar S*
(12) fin_proc
\end{verbatim}

Donde \texttt{asignar\_centroide\_mas\_cercano}, asigna como centroide
a cada vector del conjunto de datos al más cercano según la métrica
asociada.

Y donde \texttt{recomputar\_centroides}, mueve cada centroide del estado \texttt{S}
a su centro geométrico.

\subsection{Simulated Annealing (SA)} \label{SA}

"Simulated Annealing" es una metaheurística de trayectoria inspirada en
la técnica denominada "annealing" en metalurgia, en la cuál se calienta
y se enfría progresivamente un material con el fin de incrementar el
tamaño de sus cristales y disminuir sus defectos.

Esta metaheurística se diferencia de las otras pues permite que con cierta
probabilidad de un estado se tome uno de sus vecinos que no mejoran la solución.
Esta probabilidad desciende progresivamente. La variable denominada "temperatura"
funciona para este fin: Altos valores de la temperatura llevarán a altas probabilidades
de ir a un vecino que no mejore la solución, mientras que bajas temperaturas lo evitarán.

El pseudo-código del procedimiento implementado es el siguiente:

\begin{verbatim}
( 1) proc simulated_annealing():
( 2)     S <- solución_Inicial()
( 3)     S* <- S
( 4)     K <- K_0
( 5)     T <- T_0
( 6)     mientras( no criterio_de_parada ) hacer
( 7)         k <- 0
( 8)         a <- 0
( 9)         mientras( k < K y a < A ) hacer
(10)             S' <- obtener_vecino_al_azar(S)
(11)             si criterio_de_aceptación(S,S') entonces
(12)                 S <- S'
(13)                 a <- a+1
(14)                 si criterio_de_aceptación(S*,S') entonces
(15)                     S* <- S'
(16)                 fin_si
(17)             si_no
(18)             si( rand() < exp( -|c(S')-c(S)|/T ) ) entonces
(19)                 S <- S'
(20)                 a <- a+1
(21)             fin_si
(22)         fin_mientras
(23)         T <- T * alpha
(24)         K <- K * ro
(25)     fin_mientras
(26)     retornar S*
(27) fin_proc
\end{verbatim}

A continuación se realizará una explicación de las subrutinas implementadas:

\begin{itemize}
    \item En la línea (3), la variable $S*$ contendrá la mejor solución
    encontrada.
    \item En la línea (4), la variable $K$ contendrá el número de
    iteraciones que se realizarán para una determinada temperatura. La variable
    $K\_0$ contendrá el valor predeterminado para dicho número de iteraciones.
    \item En la línea (5), la variable $T$ contendrá la temperatura actual. La
    variable $T\_0$ contendrá la temperatura inicial predeterminada.
    \item En la línea (6), el criterio de parada implementado fue solamente un
    contador de iteraciones. De modo que el algoritmo detiene su ejecución después
    de ese número de ciclos.
    \item En la línea (7), la variable $k$ es un contador de iteraciones. Se
    utiliza para medir que se hagan $K$ iteraciones en los ciclos internos para
    cada temperatura.
    \item En la línea (8), la variable $a$ sirve para medir el número máximo
    de aceptaciones que se realizarán en un sub-cilco para una temperatura
    determinada. Una aceptación ocurre cuando se decide trasladarse a un
    vecino de la solución actual. Independientemente si dicha solución
    mejora o no a la anterior.
    \item En la línea (9), hasta la (22) se realiza un ciclo interno cuya
    finalidad es realizar movimientos dentro de la vecindad del estado
    en análisis $S$ para una misma temperatura. Al final de dicho ciclo
    se disminuirá la temperatura y aumentará el número de iteraciones realizadas.
    \item En la línea (14), se actualiza la variable $S*$ para que siempre contenga
    la mejor solución encontrada hasta el momento.
    \item En la línea (18), el procedimiento $rand()$ retorna un número al azar
    en el rango $[0,1)$. El procedimiento $c(S)$ retorna el criterio de calidad
    de la solución que se le da como parámetro.
    \item En la línea (23), se disminuye el valor de la temperatura en cierto
    porcentaje. La variable $alpha$ contiene un valor predefinido en el rango
    $[0.8,0.99]$.
    \item En la línea (24), se aumenta el número de iteraciones realizado en
    los ciclos internos. La variable $ro$ tiene un valor predefinido de $1.01$.

\end{itemize}

Se puede apreciar que la metaheurística va disminuyendo progresivamente las
posibilidades de realizar movimientos a soluciones que empeoren la solución
global. La metaheurística presenta un muy buen comportamiento pero toma
más tiempo que las otras metaheurísticas de trayectoria, ya que se debe
disminuir la temperatura de manera lenta para que se garantice que se
consiga una buena solución.

\section{Descripción de las Metaheurísticas Constructivas Implementadas}

Para el caso de las metaheurísticas constructivas, utilizamos la versión original
del problema, donde no se fijan de antemano el número de clusters que debe tener
la solución. Esto, dado que la naturaleza de las metaheurísticas implementadas
se basan en la premisa de que los clusters se irán creando y destruyendo según
sea conveniente.

Este problema es naturalmente más general, dado que estamos identificando
patrones sin conocer de antemano el número de grupos que deseamos formar.
Sin embargo, nuestra implementación varía automáticamente entre qué versión
utilizar; para aquellas metaheurísticas que lo exijan, será necesario fijar
el número de clusters mientras que para las constructivas, este número
será decidido por la misma metaheurística.

En el caso de las metaheurísticas constructivas se probó fundamentalmente
con dos, una versión de colonia de hormigas denominada \textit{AntClust Algorithm},
propuesta por Ouadfel y Batouch y una metaheurística híbrida propuesta por
nosotros.

\bigskip
Entre los problemas encontrados con el uso de este tipo de metaheurísticas es,
que dado que nuestro criterio de bondad de una solución decrece a medida de
que el número de clusters vacíos aumenta, la metaheurística tendía a crear un
gran número de clusters que terminaban siendo vacíos. Dado que estos clusters
no aportan algo a la solución real se modificó la metaheurística para
filtrar aquellos clusters vacíos realizando un procedimiento hasta punto
fijo de balanceo de centroides con el uso de k-means y filtrado de clusters
vacíos.

Otro problema encontrado fue que esta metaheurística no propone una solución
basada en centroides tal como hemos venido trabajando, sino una basada en
la asignación de datos a clusters. Para poder lidiar con esta diferencia,
dejamos ejecutar la metaheurística original y, posteriormente, transformamos
esta solución en una versión de nuestro problema, considerando por cada
cluster su centro geométrico.

\subsection{AntClust Algorithm (ACA)}

Esta metaheurística, al igual que la metaheurística
Ant Colony Optimization (ACO) se inspira en el comportamiento
de las colonias de hormigas. Sin embargo, ACA se inspira
principalmente en su poder de organización, más allá de su
poder de búsqueda de comida, tal como lo hace ACO.

\bigskip
El esquema general de esta metaheurística es el siguiente:
inicialmente, cada dato se encuentra individualmente en un
grupo diferente. Cada hormiga en la colonia, selecciona un
dato libre y retorna a su hormiguero. Luego, durante un
proceso iterativo, una hormiga es seleccionada aleatoriamente,
desarrolla un número de movimientos entre su hormiguero
y el espacio donde se encuentran los datos y decide probabilísticamente
si soltar o no el dato. Si la hormiga se vuelve libre (no está
cargando ningún dato) busca un nuevo dato que cargar.

Este proceso se repite hasta que se cumpla un cierto critero
de parada, regularmente un cierto número de iteraciones.

Luego de esto, procedemos a transformar este problema a nuestra
versión con centroides y a realizar el filtrado.

El criterio de elección que utiliza una hormiga para recoger
o liberar un dato viene dado por la similitud de este con
los otros elementos del cluster del cual lo está sacando o
introduciendo respectivamente. Donde definimos la función
de similitud de un dato $p_i$ en un cluster $c_k$
como:

$$ f(p_i, c_k) = \dfrac{1}{n_k} \Sigma_{p_j \in c_k}
		\dfrac{\alpha^2}{\alpha^2 + d(p_i,p_j)^2}$$

con

$$ \alpha = \dfrac{1}{N(N-1)} \Sigma_{1\leq i \leq N} \Sigma_{1\leq j \leq N} d(p_i,p_j)$$

Es decir, la similitud de un dato $p_i$ en un cluster $c_k$ será mayor mientras
menor sea el promedio de la distancia entre los elementos del cluster. Este
criterio es únicamente intracluster y no considera la componente de qué
tan disímiles son los clusters entre ellos.

\bigskip
Podemos definir inicialmente la metaheurística como:

\begin{verbatim}
( 1) proc ACA():
( 2)     asignar_datos_individualmente()
( 2)     
( 3)     Para cada hormiga a(i):
( 4)        seleccionar_dato_libre(a(i))
( 5)        volver_colonia(a(i))
( 6)     
( 7)     proceso_iterativo()
( 8)
( 9)     S <- transformar_problema()
(10)     mientras !punto_fijo:
(11)         S <- filtrado(S)
(12)         S <- k_means(S)
(13) fin_proc
\end{verbatim}

Donde podemos definir el proceso iterativo como:

\begin{verbatim}
( 1) proc proceso_iterativo():
( 2)     mientras !criterio_parada:
( 2)         Para cada hormiga:
( 3)             a(i) = hormiga seleccionada aleatoriamente
( 4)             Si a(i) carga dato(i) entonces:
( 5)                 c(k) = cluster selecto aleatoriamente
( 6)                 Si ( random <= P_drop( dato(i), c(k) ):
( 7)                     mover a(i) a c(k) y soltar dato(i)
( 8)             Sino:
( 9)                 dato(i) = dato libre selec aleatoriamente
(10)                 c(k) = cluster donde esta dato(i)
(11)                 Si ( random <= P_pick( dato(i), c(k) ):
(12)                     mover a(i) a c(k) y agarrar dato(i)
(13)         Mover a(i) al hormiguero
(13) fin_proc
\end{verbatim}

Adicionalmente la probabilidad de agarrar un dato viene dada por:

\bigskip
$$p_{pick}(p_i,c_k) =
	\begin{cases}
		1, & \mbox{si } |c_k|\mbox{ = 1} \\
		q, & \mbox{si } |c_k|\mbox{ = 2} \\
		cos^2 \left( \dfrac{\pi}{2}f(p_i,c_k) \right) &  \mbox{en otro caso}\\
    \end{cases}
$$

donde $q$ es una constante entre 0 y 1 regularmente alta.

Y la probabilidad de liberarlo viene dada por:

\bigskip
$$p_{drop}(p_i,c_k) =
		1 - cos^2 \left( \dfrac{\pi}{2}f(p_i,c_k) \right)\\
$$

\subsection{AntClust Hybrid Algorithm (ACHA)}

Esta metaheurística es presentada por nosotros como una
combinación de la metaheurística antes propuesta AntClust
Algorithm (ACA) con la metaheurística de intensificación
ILS y, finalmente, una nueva pasada de filtrado de clusters
vacíos en conjunción con k-means.

El objetivo de esta metaheurística es poder intensificar
aún más las soluciones obtenidas por las metaheurísticas
constructivas que, podría darse el caso, no han convergido
a un óptimo.

Podemos definir el pseudocódigo de esta metaheurística como:

\begin{verbatim}
( 1) proc ACHA():
( 2)     S <- ACA()
( 2)     S <- ILS(S)
( 3)     
( 4)     mientras !punto_fijo:
( 5)         S <- filtrado(S)
( 6)         S <- k_means(S)
( 7) fin_proc
\end{verbatim}

\section{Descripción de las Metaheurísticas Poblacionales Implementadas}



\section{Experimentos y Análisis de Resultados} \label{Resultados}

\input{resultados}

\section{Conclusiones y Recomendaciones}

El problema de Clustering es sumamente diverso, complejo, variable, e interesante.
Sus aplicaciones en la vida real van desde áreas de la biología, a áreas de análisis
estadísticos, inteligencia artificial, finanzas, y muchos otros. Lo que
diferencia este problema a otros es su propiedad de no poder ofrecer
soluciones precisas y objetivas a cada caso de prueba mediante las cuales se pueda
comparar los resultados de un algoritmo con los resultados de otro; este hecho implica que la metodología
para realizar mediciones de calidad a una solución es subjetiva y está
plenamente atada a la función de calidad implementada. Es tanta la importancia
de dicha función de calidad que la solución final dependerá al cien por ciento
de ésta: algunos criterios de calidad darán preferencia a cierto tipo de soluciones
que a otras, consecuentemente los algoritmos de búsqueda darán preferencia a las
soluciones cuya forma sea preferida por el medidor de bondad de clusters.

La solución al problema de clustering trata de encontrar ``patrones'' en un conjunto
de observaciones y tratar de agrupar dichos datos en función de su nivel de semejanza
con respecto estos patrones ocultos que se detecten en las descripciones de varias observaciones.
En la solución que se implementó para el problema, dado que sólo se resolvió el problema
de clustering numérico, cada observación fue considerada como un punto en un plano
cartesiano \emph{N-dimensional}, de modo que todos los métodos implementados para la medición de la cercanía o de
la semejanza entre dos puntos u observaciones realmente eran medidores de la cercanía geométrica
en el plano cartesiano \emph{N-dimensional} de dichos puntos. Esta característica
podría resultar muy positiva y efectiva para ciertos conjuntos de observaciones, pero negativa para otros. Por ejemplo, supóngase
un conjunto de observaciones que describen puntos en distintas espirales en un plano;
si se interpreta dichas observaciones como puntos en un plano cartesiano, se intentará agrupar puntos
que estén cercanos, lo que implica que el algoritmo no detectará la propiedad compartida de algunos puntos
que se encuentran en una misma espiral. Sin embargo, si las observaciones son interpretadas
como puntos en un plano de coordenadas polares, la propiedad de encontrarse descrito por una misma espiral
podrá ser detectada por la solución al problema y así se descubrirá patrones entre los datos
que no se habían descubierto anteriormente o a simple vista.

El análisis anterior permite afirmar que para realizar algoritmos de clustering más acertivos
es necesario ``expandir las dimensiones'' de los datos encontrados para así lograr
encontrar patrones ocultos en ellos. Esta premisa sugiere realizar
transformaciones a los datos que los relacionen unos con otros; agregar más datos a cada
observación, y que cada uno de estos datos adicionales esté en función de los datos
originales. De esta manera se aumentará la probabilidad de encontrar relaciones
interesantes entre los datos que lleven a conclusiones de la relación entre estos.

Finalmente, cabe destacar que el problema de clustering no es un problema muerto, aún se realiza mucha investigación
al respecto debido a la amplia aplicación de éste en la industria y la academia.

\bigskip
Como recomendación específica para las metaheurísticas constructivas,
se trata de buscar establecer límites en el número de clusters que se
desean obtener. Para esto, se ha pensado en realizar clustering sobre
los centroides obtenidos por las metaheurísticas, para agruparlos y
formar particiones de menos conjuntos. Sin embargo, esto no ha sido
implementado aún, por lo cual constituye una meta para futuras entregas.

%\begin{thebibliography}{99}
%\bibitem{Cook}Cook, Stephen: ``The complexity of theorem-proving
%  procedures''. \emph{ACM}, 1971.
%\end{thebibliography}

\end{document}
